<TITLE>prob002: template design</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob002: template design</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.scs.leeds.ac.uk/bms/home.html">
          <B>Barbara Smith</B></A> 
          <ADDRESS><a href="mailto:bms@scs.leeds.ac.uk">
          bms@scs.leeds.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>
<P>

Solutions for the problems in the data files are given in
<A HREF="file://www.scs.leeds.ac.uk/scs/doc/reports/1997/97_16.ps.Z">
Proll and Smith (1997)
</A>.
Most
solutions given there for the magazine inserts problem are not known to be
optimal. 

<P>

This problem appears to be difficult for both ILP and CP.
For ILP, this is because the problem cannot 
easily be expressed in terms of linear constraints.
Whilst CP can in principle handle non-linear constraints, 
a straightforward formulation with only sufficient constraints to 
ensure that solutions are correct appears to be practical only 
for the smallest problems. For the larger problems, whilst it is 
possible to find solutions which cannot be far from optimal by using
a more sophisticated approach, proving optimality or finding 
better solutions has so far proved impossible. 

<P>

<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


